package 力扣.排序.快速排序;

import sun.security.krb5.internal.crypto.Aes128;

import java.util.Arrays;

public class 模板 {
    public static void main(String[] args) {
//       int[] nums = {3,4,5,2,5,6,2,65,123,0};
       int[] nums = {3,2,4,1};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
     static void quickSort(int[] nums){
        if (nums == null){
            return;
        }
        qsort(nums,0, nums.length);
    }

    /**
      边中切递（三餐）
     */
    static void qsort(int[] A,int b,int e){//左闭右开
        if (b >= e || b + 1 >= e){//b>=e:表示空区间 (b+1)>=e:表示就剩一个元素
            return;
        }
        int m = b + ((e - b) >> 1);
        int x = A[m];//中间元素 注意：中间元素要放在循环的外面

        //三路切分
        int l = b, i = b, r = e - 1;
        while (i <= r){
            if (A[i] > x){//中间元素’x‘要放在循环的外面（血的教训！！！）
                swap(A, l++, i++);
            }else if (A[i] == x){
                i++;
            }else{
                swap(A, i, r--);
            }
        }
        //类似于二叉树的前序遍历，分别递归遍历左右子树
        qsort(A, b, l);//左区间
        qsort(A, i, e);//右区间
    }
    static void swap(int[] A,int i,int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }

}
